package 动态规划;

//最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：
//    Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
//    Paste (粘贴) : 你可以粘贴你上一次复制的字符。
//给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。
// 输出能够打印出 n 个 'A' 的最少操作次数。
public class 只有两个键的键盘 {

    public static int minSteps(int n) {
        int res=0;
        for (int i = 2; i <=n ; i++) {
            while (n%i==0){
                res+=i;
                n/=i;
            }
        }
        return res;
    }
    public static int minSteps1(int n) {
        int[] dp = new int[n + 1];
        dp[0]=dp[1]=0;
        for (int i = 2; i < n+1; i++) {
            //如果是质数，则执行i次操作。如果是合数，则找到最大公约数，在执行i/j次，因为i/j一定是质数，所以可以换成dp[i/j]
            dp[i]=i;
            for (int j = i/2; j>=Math.sqrt(i) ; j--) {
                if (i%j==0) {
                    dp[i] = dp[j] + dp[i / j];
                    break;
                }
            }
        }
        return dp[n];
    }
}
